//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 示例 4： 
//
// 
//输入：s = "([)]"
//输出：false
// 
//
// 示例 5： 
//
// 
//输入：s = "{[]}"
//输出：true 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 仅由括号 '()[]{}' 组成 
// 
// Related Topics 栈 字符串 
// 👍 2957 👎 0


import java.util.Deque;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution20 {
    /**
     * 解题思路：
     * 1.利用数据模拟栈结构
     * 2.遍历元素字符串 如果是 ({[ 则放入数组，index+1;
     * 3.如果是 )]}, 如果index=0.说明没有匹配的前括号，return false，
     *  取出前一个元素，如果与括号不匹配，returnfalse，
     *  如果匹配， index-1
     * 4.最终栈中无元素则说明全部匹配成功
     *
     * 解答成功:
     * 			执行耗时:0 ms,击败了100.00% 的Java用户
     * 			内存消耗:38.9 MB,击败了17.61% 的Java用户
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        char[] stack = new char[chars.length];
        int index = 0;

        for (char aChar : chars) {
            if(aChar == '(' || aChar == '[' || aChar == '{') {
                stack[index++] = aChar;
            }
            if(aChar == ')' || aChar == ']' || aChar == '}') {
                if(index == 0) return false;
                char c = stack[index-1];
                if((aChar == ')' && c == '(') ||
                        (aChar == ']'&& c == '[') ||
                        (aChar == '}' && c == '{')) {
                    index--;
                } else {
                    return false;
                }
            }
        }

        return index == 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
